//数组arr是[0, 1, ..., arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连
//接的结果和按升序排序后的原数组相同。 
//
// 我们最多能将数组分成多少块？ 
//
// 示例 1: 
//
// 输入: arr = [4,3,2,1,0]
//输出: 1
//解释:
//将数组分成2块或者更多块，都无法得到所需的结果。
//例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
// 
//
// 示例 2: 
//
// 输入: arr = [1,0,2,3,4]
//输出: 4
//解释:
//我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
//然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
// 
//
// 注意: 
//
// 
// arr 的长度在 [1, 10] 之间。 
// arr[i]是 [0, 1, ..., arr.length - 1]的一种排列。 
// 
// Related Topics 栈 贪心 数组 排序 单调栈 
// 👍 161 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class MaxChunksToMakeSorted {
    public static void main(String[] args) {
        int[] nums  = {0,1,2,4,3};
        new MaxChunksToMakeSorted().new Solution().maxChunksToSorted(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 先进行分块，再将前块的最大值和后块的最小值进行比较，每个块间必须按照升序进行才对
     * 实现起来过于麻烦，且没有成功，脑袋瓜子嗡嗡的，md
     */
    public int myMaxChunksToSorted(int[] arr) {

        if (arr.length == 1) return 1;
        List<Integer> minList = new LinkedList<>();
        List<Integer> maxList = new LinkedList<>();
        for (int i = 0; i < arr.length;) {
            if (i == arr.length-1){
                if (arr[i]>arr[i-1]){
                    minList.add(arr[i]);
                    maxList.add(arr[i]);
                }else {
                    Integer[] minL = minList.toArray(new Integer[minList.size()]);
                    minL[minL.length-1] = arr[i];
                }
                break;
            }
            for (int j = i+1; j < arr.length ; j++) {
                if (arr[i]<arr[j]){
                    maxList.add(arr[i]);
                    minList.add(arr[j-1]);
                    i = j;
                    break;
                }
                if (j+1 == arr.length) {
                    minList.add(arr[j]);
                    maxList.add(arr[i]);
                    i = arr.length;
                }
            }
            if (i == 0) return 1;
        }
        Integer[] minL = minList.toArray(new Integer[minList.size()]);
        Integer[] maxL = maxList.toArray(new Integer[maxList.size()]);
        if (minL.length!=1){
            for (int i = 0; i < minL.length - 1 ; i++) {
                if (maxL[i]>minL[i+1]) return 1;
            }
        }
        return minL.length;

    }

    /**
     * 看题解
     * 暴力算法，也是统计连续的递增区间
     * 再计数时只需要判断当前值是否为max就行了
     * 比如1 2 0 3 只有在 1 2 和 3 的时候会进行计数
     * 而4 3 2 1 0 则只会在4的时候进行计数
     * 所有连续降序的区间排列的区间只会统计一次
     */
    public int maxChunksToSorted(int[] arr){
        int ans = 0, max = 0;
        for (int i = 0; i < arr.length; ++i) {
            max = Math.max(max, arr[i]);
            if (max == i) ans++;
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}